//https://leetcode.cn/problems/maximum-subarray-min-product/
//单调栈+前缀数组

#include <vector>
#include <iostream>
#include <stack>

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        std::vector<std::pair<int,int>> res(nums.size(),{-1,-1});
        std::stack<std::list<int>> stack;
        for(size_t i=0;i<nums.size();++i){
            while(!stack.empty()&& nums[stack.top().back()] > nums[i]) {
                std::list<int> popIs=stack.top();
                stack.pop();
                int leftlessIndex = stack.empty()? -1:stack.top().back();
                for(int popi:popIs){
                    res[popi].first = leftlessIndex;
                    res[popi].second = i;
                }
            }
            if(!stack.empty() && nums[stack.top().back()] == nums[i]) {
                stack.top().push_back(i);
            }else{
                std::list<int> list = {(int)i};
                stack.push(list);
            }
        }

        while(!stack.empty()){
            list<int> popIs=stack.top();
            stack.pop();
            int leftlessIndex = stack.empty()? -1:stack.top().back();
            for(int popi:popIs) {
                res[popi].first = leftlessIndex;
                res[popi].second = -1;
            }
        }
        
        //前缀和
        std::vector<long long > pre(nums.size(),0);
        pre[0]=nums[0];
        for(size_t i=1;i<nums.size();++i){
            pre[i]=pre[i-1]+nums[i];
        }

        long long best=0;
        for(int i=0;i<res.size();++i){
            int left= res[i].first==-1? 0:res[i].first+1;
            int right= res[i].second== -1? res.size()-1:res[i].second-1;
            long long cur_val= (pre[right]-pre[left]+nums[left])*nums[i];
            best=std::max(best,cur_val);
        }
        long long mod = 1000000007;
        return best%mod;
    }
};